Currently, a network with a wider bandwidth may carry more data. Fashion applications through the network such as network meeting, cloud computing and so on, have been received much attention as the rise of sharing and the transmitting of the screen content. Thus, it becomes important to efficiently transmit screen contents through the network. Screen contents and camera-captured images have different characteristics. Coding the screen contents needs coding tools and schemes different from traditional ones. Palette coding is one of the coding tools and schemes for coding the screen contents, which could provide good compression performances.
A test image for the screen content coding (SCC) usually contains a small number of primary colors. Palette encoding method uses this characteristic to encode the screen contents efficiency. FIG. 1 is a flowchart illustrating a palette encoding method. Referring to FIG. 1, in step S101, the palette encoding method analyzes the primary colors in a coding unit (CU). The CU is composed of pixels and each pixel has its own color values. In step S103, the palette encoding method generates a palette table. In step S105, each pixel of the CU is represented by a corresponding color index on the color index table. Then color indexes forms a color index map. In step S107, the palette table and the color index map are encoded.
FIG. 2 is an example of establishing a color index map by a palette encoding method. Referring to FIG. 2, a CU 201 is composed of 64 pixels having a total of 8 kinds of colors. The palette table may not include all kinds of colors in the CU. Therefore, the colors included in the palette table are primary colors and the colors excluded in the palette table are escape colors. For example, the palette table includes 6 primary colors C0, C1, C2, C4, C5, and C6. Therefore, colors C3 and C7 are classified as escape colors. Usually, there are few pixels that are classified as having escape colors. After the palette table has been generated, the palette encoding method generates a color index map 202 according to the palette table. The color index values from 0 to 5 in the color index map 202 correspond to the colors C0, C1, C2, C4, C5, and C6 in CU 201, respectively. The color index values from 0 to 5 are also referred as primary color index values. The color index value 6 in the color index map 202 corresponds to the two escape colors C3 and C7 in CU 201. The color index value 6 is also referred as an escape color index value. Finally, the palette table and the color index map 202 are encoded, and both the encoded palette table and the encoded color index map are transmitted to the decoder.
The palette table classifies colors having similar color values based on a size of a quantization step. For example, the color values from 1 to 100 are classified into 10 different color groups 1˜10, 11˜20, 21˜30, . . . , and 91˜100. The average value of each color group is one of primary colors in the palette table. FIG. 3 is a flowchart of a method illustrating a palette table generation based on the K-means clustering. Referring to FIG. 3, in step S301, all initial color groups are empty. In step S303, a current pixel is selected. Wherein, all pixels in the CU are processed in a raster scan order, which processes pixels of each row from left to right and processes each row from top to bottom, until all pixels in the CU are processed. Then the method classifies all pixels in the CU into different color groups, as described below. In step S305, for each color group, the method calculates a color difference between the color of the current pixel and an average value of the colors of each color group. Each color group has two parameters, wherein one is a number of pixels in the color group and the other is an average value of colors in the color group, and the initial values of both the number of pixels and the average value of colors are zero. In step S307, the method detennines whether a minimum value of the color differences between the color of the current pixel and the average value of the colors of the color groups is less than or equal to an error limit based on the size of the quantization step. When the minimum value of the color differences is less than or equal to the error limit (Step S307, Yes), the current pixel is classified into the color group having the minimum value of the color differences, the number of pixels of the color group is added by 1, and the average value of colors of the color group is re-calculated, as shown in step S309. When all the color differences are greater than the error limit (Step S307, No), the current processing pixel forms a new color group, as shown in step S311. For the new color group, the number of pixels is 1 and the average value of colors is the color value of the current pixel. After finishing processing all pixels in the CU, the palette table, according to a predetermined size S, selects S color groups having largest numbers of pixels from all color groups. The S average values of colors of the selected color groups are S primary colors on the palette table. The colors of the pixels in the un-selected color groups are escape colors.
However, some situations may occur when the primary colors are generated by using the K-means clustering. FIG. 4A and FIG. 4B illustrate some of situations occurring on the color groups generated by using the K-means clustering. For a selected color group, the average value of the selected color group may drift as one or more new pixels are included. Thus, the initial color average of the selected color group may be far away from a final color average of the selected color group. For example, referring to FIG. 4A, a selected color group 410 initially has color 411, color 412, color 413, and color 415, and an initial average value of colors is an initial average color 414. With three colors 416˜418 being added into the color group 410, the average value of colors of the color group 410 changes from the initial average color 414 to another average color 419, then the average value of colors further changes from the average color 419 to a final average color 420. Therefore, the final average color 420 may be far away from the initial average color 414, and the average value of colors of the selected color group 410 drifts. In addition, a selected color group may include more than one sub groups, and these sub groups may be represented by a primary color such as the average value of colors of the selected color group. Take an example of FIG. 4B, a selected color group 430 includes a sub group 431 and a sub group 432. The sub group 431 and the sub group 432 are represented by the average value of colors of the selected color group 430 (in other words, the sub group 431 and the sub group 432 are represented by an average color 433 of the selected color group 430). Therefore, the color displayed by the sub group 431 and the sub group 432 is the average color 433 that is different from the original colors of the two sub groups 431 and 432.